#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

//int integerBreak(int n)
//{
//    if (n < 4)
//        return n - 1;
//    int x = n / 3;
//    switch (n % 3)
//    {
//    case 1:
//        return pow(3, x - 1) * 4;
//        break;
//    case 2:
//        return pow(3, x) * 2;
//        break;
//    case 0:
//        return pow(3, x);
//        break;
//    default:
//        break;
//    }
//    return 0;
//}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* shuffle(int* nums, int numsSize, int n, int* returnSize)
{
    *returnSize = 2 * n;
    int k = numsSize;
    int* a = (int*)malloc(sizeof(int) * n);
    int* b = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < k; i++)
    {
        if (i == k / 2)
            break;
        else
            a[i] = nums[i];
    }
    int q = 0;
    for (int i = k / 2; i < k; i++)
    {
        b[q] = nums[i];
        q++;
    }
    int t = 0;
    int p = 0;
    for (int i = 0; i < k; i++)
    {
        if (i % 2 == 0)
        {
            nums[i] = a[t];
            t++;
        }
        else
        {
            nums[i] = b[p];
            p++;
        }
    }
    return nums;
}